Adopting Inference Networks for Online Thread Retrieval.

Utilizing Context in Generative Bayesian Models for Linked Corpus.


Determining the sexual identities of prehistoric cave artists using digitized handprints a machine learning approach.


Extending Legacy Agent Knowledge Base Systems with Semantic Web Compatibilities.

oreChem ChemXSeer a semantic digital library for chemistry.

Finding algorithms in scientific articles.
Increasingly, special-purpose search engines are being built to enable the retrieval of documentelements like tables, figures, and algorithms [2, 20, 15]. These search engines present a thumbnail view of the document-elements, some document metadata like the title of the paper and its authors, and in lieu of a document snippet, typically, they present the caption of the document-element. While some authors in some disciplines write carefully tailored captions, generally, the author of a document assumes that the caption will be read in context of the text in the document. When the caption is presented out-ofcontext as in a document-element-search-engine result, it may not contain enough information to help the end-user understand what the content of the document-element is. Consequently, end-users examining document-element search results would want a short “synopsis ” of this information presented along with the document- element. Having access to the synopsis allows the end-user to quickly understand the content of the document-element without having to download and read the entire document. Furthermore, it allows the end-user to examine more results than they would otherwise. In this paper, we present the first set of methods to extract this useful information (synopsis) related to document-elements automatically. We use machine learning techniques to identify relevant sentences from the document text based
Learning Topical Transition Probabilities in Click Through Data with Regression Models.
The transition of search engine users ’ intents has been studied for a long time. The knowledge of intent transition, once discovered, can yield a better understanding of how different topics are related and be used in many applications, such as building recommender systems, ranking and etc. In this paper, we study the problem of finding the transition probabilities of digital library users ’ intents among different topics. We use the click-through data from CiteSeerX and extract the click chains. Each document in the click chain is represented by a topical vector generated by LDA models. We then model the task of finding the topical transition probabilities as a multiple output linear regression problem, in which the input and output are two consecutive topical vectors in the click chain and the elements in the weight
Context%2Daware citation recommendation.
Abstract. Scientific literature with rich metadata can be represented as a labeled directed graph. This graph representation enables a number of scientific tasks such as ad hoc retrieval or named entity recognition (NER) to be formulated as typed proximity queries in the graph. One popular proximity measure is called Random Walk with Restart (RWR), and much work has been done on the supervised learning of RWR measures by associating each edge label with a parameter. In this paper, we describe a novel learnable proximity measure which instead uses one weight per edge label sequence: proximity is defined by a weighted combination of simple “path experts”, each corresponding to following a particular sequence of labeled edges. Experiments on eight tasks in two subdomains of biology show that the new learning method significantly outperforms the RWR model (both trained and untrained). We also extend the method to support two additional types of experts to model intrinsic properties of entities: query-independent experts, which generalize the PageRank measure, and popular entity experts which allow rankings to be adjusted for particular entities that are especially important.
Learning Topical Transition Probabilities in Click Through Data with Regression Models.
The transition of search engine users ’ intents has been studied for a long time. The knowledge of intent transition, once discovered, can yield a better understanding of how different topics are related and be used in many applications, such as building recommender systems, ranking and etc. In this paper, we study the problem of finding the transition probabilities of digital library users ’ intents among different topics. We use the click-through data from CiteSeerX and extract the click chains. Each document in the click chain is represented by a topical vector generated by LDA models. We then model the task of finding the topical transition probabilities as a multiple output linear regression problem, in which the input and output are two consecutive topical vectors in the click chain and the elements in the weight
Clustering%2Dbased incremental web crawling.

Clustering%2Dbased incremental web crawling.

Uninterpreted Schema Matching with Embedded Value Mapping under Opaque Column Names and Data Values.

Distributed routing in wireless sensor networks using energy welfare metric.

11th ACM International Workshop on Web Information and Data Management %28WIDM 2009%29

Approximate Rewriting of Queries Using Views.

Learning to rank graphs for online similar graph search.
Many applications in structure matching require the ability to search for graphs that are similar to a query graph, i.e., similarity graph queries. Prior works, especially in chemoinformatics, have used the maximum common edge subgraph (MCEG) to compute the graph similarity. This approach is prohibitively slow for real-time queries. In this work, we propose an algorithm that extracts and indexes subgraph features from a graph dataset. It computes the similarity of graphs using a linear graph kernel based on feature weights learned offline from a training set generated using MCEG. We show empirically that our proposed algorithm of learning to rank graphs can achieve higher normalized discounted cumulative gain compared with existing optimal methods based on MCEG. The running time of our algorithm is orders of magnitude faster than these existing methods.
Generating synopses for document%2Delement search.

Multidimensional political spectrum identification and analysis.

Independent informative subgraph mining for graph information retrieval.
In order to enable scalable querying of graph databases, intelligent selection of subgraphs to index is essential. An improved index can reduce response times for graph queries significantly. For a given subgraph query, graph candidates that may contain the subgraph are retrieved using the graph index and subgraph isomorphism tests are performed to prune out unsatisfied graphs. However, since the space of all possible subgraphs of the whole set of graphs is prohibitively large, feature selection is required to identify a good subset of subgraph features for indexing. Thus, one of the key issues is: given the set of all possible subgraphs of the graph set, which subset of features is the optimal such that the algorithm retrieves the smallest set of candidate graphs and reduces the number of subgraph isomorphism tests? We introduce a graph search method for subgraph queries based on subgraph frequencies. Then, we propose several novel feature selection criteria, Max-Precision, Max-Irredundant-Information, and Max-Information-Min-Redundancy, based on mutual information. Finally we show theoretically and empirically that our proposed methods retrieve a smaller candidate set than previous methods. For example, using the same number of features, our method improve the precision for the query candidate set by 4%-13 % in comparison to previous methods [25, 26]. As a result the response time of subgraph queries also is improved correspondingly.
Detecting topic evolution in scientific literature how can citations help%3F
Understanding how topics in scientific literature evolve is an interesting and important problem. Previous work simply models each paper as a bag of words and also considers the impact of authors. However, the impact of one document on another as captured by citations, one important inherent element in scientific literature, has not been considered. In this paper, we address the problem of understanding topic evolution by leveraging citations, and develop citation-aware approaches. We propose an iterative topic evolution learning framework by adapting the Latent Dirichlet Allocation model to the citation network and develop a novel inheritance topic model. We evaluate the effectiveness and efficiency of our approaches and compare with the state of the art approaches on a large collection of more than 650,000 research papers in the last 16 years and the citation network enabled by CiteSeerX. The results clearly show that citations can help to understand topic evolution better.
Effectively Searching Maps in Web Documents.


Improving the Table Boundary Detection in PDFs by Fixing the Sequence Error of the Sparse Lines.
As the rapid growth of PDF documents, recognizing the document structure and components are useful for document storage, classification and retrieval. Table, a ubiquitous document component, becomes an important information source. Accurately detecting the table boundary plays a crucial role for many applications, e.g., the increasing demand on the table data search. Rather than converting PDFs to image or HTML and then processing with other techniques (e.g., OCR), extracting and analyzing texts from PDFs directly is easy and accurate. However, text extraction tools face a common problem: text sequence error. In this paper, we propose two algorithms to recover the sequence of extracted sparse lines, which improve the table content collection. The experimental results show the comparison of the performance of both algorithms, and demonstrate the effectiveness of text sequence recovering for the table boundary detection. 1.

Dewey Decimal System.
This guide provides a selected list of Social Issues resources available in the Savidge/Bowers library and on the Out-of-Door Academy website The Dewey Decimal System classifications for sociology and society issues range from 300 to 361. You can browse in the subject classification in the Library
LOC METS.
In order to perform meaningful experiments in optimizing compilation and runtime system design, researchers usually rely on a suite of benchmark programs of interest to the optimization technique under consideration. Programs are described as numeric, memory-intensive, concurrent, or object-oriented, based on a qualitative appraisal, in some cases with little justification. In order to make these intuitive notions of program behaviour more concrete and sub-ject to experimental validation, this thesis introduces a methodology to objectively quantify key aspects of program behaviour using dynamic metrics. A set of unambiguous, dynamic, robust and architecture-independent dynamic metrics is defined, and can be used to cate-gorize programs according to their dynamic behaviour in five areas: size, data structures, memory use, polymorphism and concurrency. Each metric is also empirically validated. A general-purpose, easily extensible dynamic analysis framework has been designed and implemented to gather empirical metric results. This framework consists of three major components. The profiling agent collects execution data from a Java virtual machine. The
Citation.
The importance of a Web page is an inherently subjective matter, which depends on the readers interests, knowledge and attitudes. But there is still much that can be said objectively about the relative importance of Web pages. This paper describes PageRank, a method for rating Web pages objectively and mechanically, effectively measuring the human interest and attention devoted to them. We compare PageRank to an idealized random Web surfer. We show how to efficiently compute PageRank for large numbers of pages. And, we show how to apply PageRank to search and to user navigation.
Dewey Decimal System.
This guide provides a selected list of Social Issues resources available in the Savidge/Bowers library and on the Out-of-Door Academy website The Dewey Decimal System classifications for sociology and society issues range from 300 to 361. You can browse in the subject classification in the Library
Dublin Core.

Dublin Core.

Effectively Searching Maps in Web Documents

Automated analysis of images in documents for intelligent document search.
analysis of images in documents for intelligent
Hierarchical Location and Topic Based Query Expansion.

Automatic Extraction of Data Points and Text Blocks from 2%2DDimensional Plots in Digital Documents.
Two dimensional plots (2-D) in digital documents on the web are an important source of information that is largely under-utilized. In this paper, we outline how data and text can be extracted automatically from these 2-D plots, thus eliminating a time consuming manual process. Our information extraction algorithm identifies the axes of the figures, extracts text blocks like axes-labels and legends and identifies data points in the figure. It also extracts the units appearing in the axes labels and segments the legends to identify the different lines in the legend, the different symbols and their associated text explanations. Our algorithm also performs the challenging task of separating out overlapping text and data points effectively. Our experiments indicate that these techniques are computationally efficient and provide acceptable accuracy.


Metadata extraction and indexing for map search in web documents.
The World Wide Web is growing and changing at an astonishing rate. Web information systems such as search engines have to keep up with the growth and changes of the Web. This thesis studies in a Web search engine how a crawler with limited computing resource can effectively crawl from the dynamically changing Web and acquire the most updated Web documents, and how a Web search engine can provide information-object–oriented indexing methods which enable users to retrieve desired information with high accuracy and high efficiency. To address the first problem, existing solutions apply sampling techniques at the website level. That means, the crawler chooses a few webpages from each website as samples and then re-downloads all the webpages in the website with the largest number of changed samples. We argue that the level of a website may not be a good granularity for sampling because the update patterns of various webpages within the same website could be quite different, while webpages with similar update patterns may distribute across different websites. We design a set of sampling policies
Real%2Dtime data pre%2Dprocessing technique for efficient feature extraction in large scale datasets.
Due to the continuous and rampant increase in the size of domain specific data sources, there is a real and sustained need for fast processing in time-sensitive applications, such as medical record information extraction at the point of care, genetic feature extraction for personalized treatment, as well as off-line knowledge discovery such as creating evidence based medicine. Since parallel multi-string matching is at the core of most data mining tasks in these applications, faster on-line matching in static and streaming data is needed to improve the overall efficiency of such knowledge discovery. To solve this data mining need not efficiently handled by traditional information extraction and retrieval techniques, we propose a Block Suffix Shifting-based approach, which is an improvement over the state of the art multi-string matching algorithms such as Aho-Corasick, Commentz-Walter, and Wu-Manber. The strength of our approach is its ability to exploit the different block structures of domain specific data for off-line and online parallel matching. Experiments on several real world datasets show how our approach translates into significant performance improvements.

A Fast Preprocessing Method for Table Boundary Detection Narrowing Down the Sparse Lines Using Solely Coordinate Information.


Segregating and extracting overlapping data points in two%2Ddimensional plots.
Most search engines index the textual content of documents in digital libraries. However, scholarly articles frequently report important findings in figures for visual impact and the contents of these figures are not indexed. These contents are often invaluable to the researcher in various fields, for the purposes of direct comparison with their own work. Therefore, searching for figures and extracting figure data are important problems. To the best of our knowledge, there exists no tool to automatically extract data from figures in digital documents. If we can extract data from these images automatically and store them in a database, an end-user can query and combine data from multiple digital documents simultaneously and efficiently. We propose a framework based on image analysis and machine learning to extract information from 2-D plot images and store them in a database. The proposed algorithm identifies a 2-D plot and extracts the axis labels, legend and the data points from the 2-D plot. We also segregate overlapping shapes that correspond to different data points. We demonstrate performance of individual algorithms, using a combination of generated and real-life images.
Finding a Haystack in Haystacks %2D Simultaneous Identification of Concepts in Large Bio%2DMedical Corpora.
Since nearly all information is now created digitally, large text databases have become more prevalent than ever. Automatically mining information from these databases proves to be a challenge due to slow pattern/string matching techniques. In this paper we introduce a new, fast multi-string pattern matching method called the Block Suffix Shifting (BSS) algorithm, which is based on the well known Aho-Chorasick algorithm. The advantages of our algorithm include: the ability to exploit the natural structure of text, perform significant character shifting, avoid useless backtracking jumps, efficient matching time and avoid the typical ”sub-string” false positive errors. Our algorithm is applicable to many fields with free text, such as the health care domain and the scientific document field. In this paper, we apply the BSS algorithm to health care data and mine hundreds of thousands of medical concepts from a large Electronic Medical Record (EMR) corpora simultaneously and efficiently. Experimental results show the superiority of our algorithm when compared with the top of the line multi-string matching algorithms (the Aho-Corasick and the Wu-Manber algorithm). 1
Mining
We are given a large database of customer transactions, where each transaction consists of customer-id, transaction time, and the items bought in the transaction. We introduce the problem of mining sequential patterns over such databases. We present three algorithms to solve this problem, and empirically evaluate their performance using synthetic data. Two of the proposed algorithms, AprioriSome and AprioriAll, have comparable performance, albeit AprioriSome performs a little better when the minimum number of customers that must support a sequential pattern is low. Scale-up experiments show that both AprioriSome and AprioriAll scale linearly with the number of customer transactions. They also have excellent scale-up properties with respect to the number of transactions per customer and the number of items in a transaction. 1 Introduction Database mining is motivated by the decision support problem faced by most large retail organizations. Progress in bar-code technology has made it po...
Towards Click%2DBased Models of Geographic Interests in Web Search.

Automatic Identification and Data Extraction from 2%2DDimensional Plots in Digital Documents

Proceedings of the First Workshop on CyberInfrastructure Information Management in eScience

Temporal and Information Flow Based Event Detection from Social Text Streams.

TableRank A Ranking Algorithm for Table Search and Retrieval.

Incremental adaptation of XPath access control views.

HICCUP Hierarchical Clustering Based Value Imputation using Heterogeneous Gene Expression Microarray Datasets.

Designing clustering%2Dbased web crawling policies for search engine crawlers.

ChemXSeer a digital library and data repository for chemical kinetics.

Facilitating situation assessment through gir with multi%2Dscale open source web documents.

Automatic Extraction of Data from 2%2DD Plots in Documents.
Two-dimensional (2-D) plots in digital documents contain important information. Often, the results of scientific experiments and performance of businesses are summarized using plots. Although 2-D plots are easily understood by human users, current search engines rarely utilize the information contained in the plots to enhance the results returned in response to queries posed by endusers. We propose an automated algorithm for extracting information from line curves in 2-D plots. The extracted information can be stored in a database and indexed to answer end-user queries and enhance search results. We have collected 2-D plot images from a variety of resources and tested our extraction algorithms. Experimental evaluation has demonstrated that our method can produce results suitable for real world use. 1.
Predicting Blogging Behavior Using Temporal and Social Networks.

Query Expansion Using Topic and Location.

Efficiently Detecting Webpage Updates Using Samples.

TableSeer automatic table metadata extraction and searching in digital libraries.
Tables are ubiquitous in digital libraries. In scientific documents, tables are widely used to present experimental results or statistical data in a condensed fashion. However, current search engines do not support table search. The difficulty of automatic extracting tables from un-tagged documents, the lack of a universal table metadata specification, and the limitation of the existing ranking schemes make table search problem challenging. In this paper, we describe TableSeer, a search engine for tables. TableSeer crawls digital libraries, detects tables from documents, extracts tables metadata, indexes and ranks tables, and provides a userfriendly search interface. We propose an extensive set of medium-independent metadata for tables that scientists and other users can adopt for representing table information. In addition, we devise a novel page box-cutting method to improve the performance of the table detection. Given a query, TableSeer ranks the matched tables using an innovative ranking algorithm – TableRank. TableRank rates each &lt;query, table&gt; pair with a tailored vector space model and a specific term weighting scheme. Overall, T ableSeer eliminates the burden of manually extract table data from digital libraries and enables users to automatically examine tables. We demonstrate the value of TableSeer with empirical studies on scientific documents.
Maximum Energy Welfare Routing in Wireless Sensor Networks.

Topic segmentation with shared topic detection and alignment of multiple documents.
Topic detection and tracking [26] and topic segmentation [15] play an important role in capturing the local and sequential information of documents. Previous work in this area usually focuses on single documents, although similar multiple documents are available in many domains. In this paper, we introduce a novel unsupervised method for shared topic detection and topic segmentation of multiple similar documents based on mutual information (MI) and weighted mutual information (WMI) that is a combination of MI and term weights. The basic idea is that the optimal segmentation maximizes MI(or WMI). Our approach can detect shared topics among documents. It can find the optimal boundaries in a document, and align segments among documents at the same time. It also can handle single-document segmentation as a special case of the multi-document segmentation and alignment. Our methods can identify and strengthen cue terms that can be used for segmentation and partially remove stop words by using term weights based on entropy learned from multiple documents. Our experimental results show that our algorithm works well for the tasks of single-document segmentation, shared topic detection, and multi-document segmentation. Utilizing information from multiple documents can tremendously improve the performance of topic segmentation, and using WMI is even better than using MI for the multi-document segmentation.
Automatic searching of tables in digital libraries.

Designing efficient sampling techniques to detect webpage updates.

Deriving knowledge from figures for digital libraries.
Figures in digital documents contain important information. Current digital libraries do not summarize and index information available within figures for document retrieval. We present our system on automatic categorization of figures and extraction of data from 2-D plots. A machine-learning based method is used to categorize figures into a set of predefined types based on image features. An automated algorithm is designed to extract data values from solid line curves in 2-D plots. The semantic type of figures and extracted data values from 2-D plots can be integrated with textual information within documents to provide more effective document retrieval services for digital library users. Experimental evaluation has demonstrated that our system can produce results suitable for real-world use.
Image annotation by hierarchical mapping of features.

Extraction and search of chemical formulae in text documents on the web.
Often scientists seek to search for articles on the Web related to a particular chemical. When a scientist searches for a chemical formula using a search engine today, she gets articles where the exact keyword string expressing the chemical formula is found. Searching for the exact occurrence of keywords during searching results in two problems for this domain: a) if the author searches for CH4 and the article has H4C, the article is not returned, and b) ambiguous searches like “He ” return all documents where Helium is mentioned as well as documents where the pronoun “he” occurs. To remedy these deficiencies, we propose a chemical formula search engine. To build a chemical formula search engine, we must solve the following problems: 1) extract chemical formulae from text documents, 2) index chemical
A clustering%2Dbased sampling approach for refreshing search engine%27s database.

Are your citations clean%3F
If the are, only one can refer to a distinct document; if not, many can refer to the same document.
Privacy%2Dpreserving semantic interoperation and access control of heterogeneous databases.
Today, many applications require users from one organization to access data belonging to organizations. While traditional solutions offered for the federated and mediated databases facilitate this by sharing metadata, this may not be acceptable for certain organizations due to privacy concerns. In this paper, we propose a novel solution – Privacypreserving Access Control Toolkit (PACT)  – that enables privacy-preserving secure semantic access control and allows sharing of data among heterogeneous databases without having to share metadata. PACT uses encrypted ontologies, encrypted ontology-mapping tables and conversion functions, encrypted role hierarchies and encrypted queries. The encrypted results of queries are sent directly from the responding system to the requesting system, bypassing the mediator to further improve the security of the system. PACT provides semantic access control using ontologies and semantically expanded authorization tables at the mediator. One of the distinguishing features of the PACT is that it requires very little changes to underlying databases. Despite using encrypted queries and encrypted mediation, we demonstrate that PACT provides acceptable performance. 1.
Automatic categorization of figures in scientific documents.
Figures are very important non-textual information contained in scientific documents. Current digital libraries do not provide users tools to retrieve documents based on the information available within the figures. We propose an architecture for retrieving documents by integrating figures and other information. The initial step in enabling integrated document search is to categorize figures into a set of pre-defined types. We propose several categories of figures based on their functionalities in scholarly articles. We have developed a machine-learning-based approach for automatic categorization of figures. Both global features, such as texture, and part features, such as lines, are utilized in the architecture for discriminating among figure categories. The proposed approach has been evaluated on a testbed document set collected from the CiteSeer scientific literature digital library. Experimental evaluation has demonstrated that our algorithms can produce acceptable results for realworld use. Our tools will be integrated into a scientificdocument digital library.
Automatic extraction of table metadata from digital documents.
Tables are used to present, list, summarize, and structure important data in documents. In scholarly articles, they are often used to present the relationships among data and highlight a collection of results obtained from experiments and scientific analysis. In digital libraries, extracting this data automatically and understanding the structure and content of tables are very important to many applications. Automatic identification extraction, and search for the contents of tables can be made more precise with the help of metadata. In this paper, we propose a set of mediumindependent table metadata to facilitate the table indexing, searching, and exchanging. To extract the contents of tables and their metadata, an automatic table metadata extraction algorithm is designed and tested on PDF documents.
Efficient Object Retrieval from Parallel Air Channels in the Presence of Replicated Objects.

Semantic access control for information interoperation.

In%2Dbroker Access Control Towards Efficient End%2Dto%2DEnd Performance of Information Brokerage Systems.

An architecture for creating collaborative semantically capable scientific data sharing infrastructures.
Increasingly, scientists are seeking to collaborate and share data among themselves. Such sharing is can be readily done by publishing data on the World-Wide Web. Meaningful querying and searching on such data depends upon the availability of accurate and adequate metadata that describes the data and the sources of the data. In this paper, we outline the architecture of an implemented cyber-infrastructure for chemistry that provides tools for users to upload datasets and their metadata to a database. Our proposal combines a two level metadata system with a centralized database repository and analysis tools to create an effective and capable data sharing infrastructure. Our infrastructure is extensible in that it can handle data in different formats and allows different analytic tools to be plugged in.
Rewriting queries using views in the presence of arithmetic comparisons.
We consider the problem of answering queries using views, where queries and views are conjunctive queries with arithmetic comparisons over dense orders. Previous work only considered limited variants of this problem, without giving a complete solution. We first show that obtaining equivalent rewritings for conjunctive queries with arithmetic comparisons is decidable. Then we consider the problem of finding maximally contained rewritings (MCR) where the decidability proof does not carry over. We investigate two special cases of this problem where the query uses only semi-interval comparisons. In both cases decidability of finding MCRs depends on the query containment test. First, we address the case where the homomorphism property holds in testing query containment. In this case decidability is easy to prove but developing an efficient algorithm is not trivial. We develop such an algorithm and prove that it is sound and complete. This algorithm applies in many cases where the query uses only left (or right) semiinterval comparisons. Then we develop a new query containment test for the case where the containing query uses both left and right semi-interval comparisons but with only one left (or right) semi interval subgoal. Based on this test, we show how to produce an MCR which is a Datalog query with arithmetic comparisons. The containment test that we develop obtains a result of independent interest. It finds another special case where query containment in the presence of arithmetic comparisons can be tested in nondeterministic polynomial time. 1
Establishing value mappings using statistical models and user feedback.
In this paper, we present a “value mapping ” algorithm that does not rely on syntactic similarity or semantic interpretation of the values. The algorithm first constructs a statistical model (e.g., co-occurrence frequency or entropy vector) that captures the unique characteristics of values and their co-occurrence. It then finds the matching values by computing the distances between the models while refining the models using user feedback through iterations. Our experimental results suggest that our approach successfully establishes value mappings even in the presence of opaque data values and thus can be a useful addition to the existing data integration techniques.
Automatic extraction of informative blocks from webpages.
Search engines crawl and index webpages depending upon their informative content. However, webpages — especially dynamically generated ones — contain items that cannot be classified as the “primary content”, e.g., navigation sidebars, advertisements, copyright notices, etc. Most end-users search for the primary content, and largely do not seek the non-informative content. A tool that assists an end-user or application to search and process information from webpages automatically, must separate the “primary content blocks ” from the other blocks. In this paper, two new algorithms, ContentExtractor, and FeatureExtractor are proposed. The algorithms identify primary content blocks by i) looking for blocks that do not occur a large number of times across webpages and ii) looking for blocks with desired features respectively. They identify the primary content blocks with high precision and recall, reduce the storage requirement for search engines, result in smaller indexes and thereby faster search times, and better user satisfaction. While operating on several thousand webpages obtained from 11 news websites, our algorithms significantly outperform the Entropy-based algorithm proposed by Lin and Ho [7] in both accuracy and run-time.
Finding Base Time%2DLine of a News Article.

Identifying Content Blocks from Web Documents.
Abstract. Intelligent information processing systems, such as digital libraries or search engines index web-pages according to their informative content. However, web-pages contain several non-informative contents, e.g., navigation sidebars, advertisements, copyright notices, etc. It is very important to separate the informative “primary content blocks” from these non-informative blocks. In this paper, two algorithms, FeatureExtractor and K-FeatureExtractor are proposed to identify the “primary content blocks ” based on their features. None of these algorithms require any supervised learning, but still can identify the “primary content blocks ” with high precision and recall. While operating on several thousand web-pages obtained from 15 different websites, our algorithms significantly outperform the Entropy-based algorithm proposed by Lin and Ho [14] in both precision and run-time.
OMEN A Probabilistic Ontology Mapping Tool.
Abstract. Most existing ontology mapping tools do not provide exact mappings. Rather, there is usually some degree of uncertainty. We describe a framework to improve existing ontology mappings using a Bayesian Network. Omen, an Ontology Mapping ENhancer uses a set of meta-rules that capture the influence of the ontology structure and the semantics of ontology relations and matches nodes that are neighbors of already matched nodes in the two ontologies. We have implemented a protype ontology matcher that can enhance existing matches between ontology concepts. Preliminary experiments demonstrate that Omen successfully identifies and enhances ontology mappings. 1
Comparative study of name disambiguation problem using a scalable blocking%2Dbased framework.
In this paper, we consider the problem of ambiguous author names in bibliographic citations, and comparatively study alternative approaches to identify and correct such name variants (e.g., &#034;Vannevar Bush&#034; and &#034;V. Vush&#034;). Our study is based on a scalable two-step framework, where step 1 is to substantially reduce the number of candidates via blocking, and step 2 is to measure the distance of two names via coauthor information. Combining four blocking methods and seven distance measures on four data sets, we present extensive experimental results, and identify combinations that are scalable and effective to disambiguate author names in citations.
Automatic extraction of informative blocks from webpages.
Search engines crawl and index webpages depending upon their informative content. However, webpages — especially dynamically generated ones — contain items that cannot be classified as the “primary content”, e.g., navigation sidebars, advertisements, copyright notices, etc. Most end-users search for the primary content, and largely do not seek the non-informative content. A tool that assists an end-user or application to search and process information from webpages automatically, must separate the “primary content blocks ” from the other blocks. In this paper, two new algorithms, ContentExtractor, and FeatureExtractor are proposed. The algorithms identify primary content blocks by i) looking for blocks that do not occur a large number of times across webpages and ii) looking for blocks with desired features respectively. They identify the primary content blocks with high precision and recall, reduce the storage requirement for search engines, result in smaller indexes and thereby faster search times, and better user satisfaction. While operating on several thousand webpages obtained from 11 news websites, our algorithms significantly outperform the Entropy-based algorithm proposed by Lin and Ho [7] in both accuracy and run-time.
Identifying Value Mappings for Data Integration An Unsupervised Approach.
Abstract. The Web is a distributed network of information sources where the individual sources are autonomously created and maintained. Consequently, syntactic and semantic heterogeneity of data among sources abound. Most of the current data cleaning solutions assume that the data values referencing the same object bear some textual similarity. However, this assumption is often violated in practice. “Two-door front wheel drive ” can be represented as “2DR-FWD ” or “R2FD”, or even as “CAR TYPE 3 ” in different data sources. To address this problem, we propose a novel two-step automated technique that exploits statistical dependency structures among objects which is invariant to the tokens representing the objects. The algorithm achieved a high accuracy in our empirical study, suggesting that it can be a useful addition to the existing information integration techniques. 1
Automatic Identification of Informative Sections of Web Pages.
Web-pages – especially dynamically generated ones – contain several items that cannot be classified as the “primary content”, e.g., navigation sidebars, advertisements, copyright notices, etc. Most clients and end-users search for the primary content, and largely do not seek the non-informative content. A tool that assists an end-user or application to search and process information from Web-pages automatically, must separate the “primary content sections ” from the other content sections. We call these sections as “Web-page blocks ” or just “blocks”. First, a tool must segment the Web-pages into Web-page blocks and second, the tool must separate the primary content blocks from the non-informative content blocks. In this paper, we formally define Web-page blocks and devise a new algorithm to partition an HTML page into constituent Web-page blocks. We then propose four new algorithms, ContentExtractor, FeatureExtractor, K-FeatureExtractor, and L-Extractor. These algorithms identify primary content blocks by (i) looking for blocks that do not occur a large number of times across Web-pages, by (ii) looking for blocks with desired features, and by (iii) using classifiers, trained with block-features respectively. While operating on several thousand Web-pages obtained from various Websites, our algorithms outperform several existing algorithms with respect to runtime and accuracy. Furthermore, we show that a Web-cache system that applies our algorithms to remove non-informative content blocks and to identify similar blocks across Web-pages can achieve significant storage savings. 1
On Containment of Conjunctive Queries with Arithmetic Comparisons.
We study the following problem: how to test if Q2 is contained in Q1, where Q1 and Q2 are conjunctive queries with arithmetic comparisons? This problem is fundamental in a large variety of database applications. Existing algorithms first normalize the queries, then test a logical implication using multiple containment mappings from Q1 to Q2. We are interested in cases where the containment can be tested more efficiently. This work aims to (a) reduce the problem complexity from PgrP2-completeness to NP-completeness in these cases; (b) utilize the advantages of the homomorphism property (i.e., the containment test is based on a single containment mapping) in applications such as those of answering queries using views; and (c) observing that many real queries have the homomorphism property. The following are our results. (1) We show several cases where the normalization step is not needed, thus reducing the size of the queries and the number of containment mappings. (2) We develop an algorithm for checking various syntactic conditions on queries, under which the homomorphism property holds. (3) We further reduce the conditions of these classes using practical domain knowledge that is easily obtainable. (4) We conducted experiments on real queries, and show that most of the queries pass this test.
An Ontology%2DComposition Algebra.

Answering Queries Using Views with Arithmetic Comparisons.
We consider the problem of answering queries using views, where queries and views are conjunctive queries with arithmetic comparisons (CQACs) over dense orders. Previous work only considered limited variants of this problem, without giving a complete solution. We have developed an ecient algorithm to obtain maximally contained rewritings (MCRs) for queries having left (or right) semi-interval-comparison predicates. For semi-interval queries we show that at least recursive datalog is necessary to nd a maximally-contained solution, and identify cases where datalog is sucient. Finally, we show that obtaining equivalent rewritings for CQAC&#039;s is decidable
An algorithm for answering queries efficiently using views.
Algorithms for answering queries using views have been used to integrate information from multiple sources. The bucket algorithm, predominantly used to reformulate queries, has two drawbacks. It generates a large number of candidate solutions, even when the number of sound solutions is small, and then checks for their soundness using an exponential conjunctive-querycontainment test. Leser [1] presents an algorithm that generates a smaller number of candidate solutions and also eliminates the conjunctive-query-containment-test, but does not guarantee the soundness of all generated solutions. We introduce the concept of shared variable buckets(SVB) covering all subgoals that share a variable in order to ensure that only sound solutions are generated and thus avoid the conjunctive-query containment test. The algorithm presented has the advantage that it avoids generation of a large set of candidate solutions whenever possible. Experimental results prove the superiority of this algorithm over previous solutions.
An Algebra for Semantic Interoperability of Information Sources.
Resolving heterogeneity among the various biological information systems is a crucial problem if we wish to gain value from the many distributed resources available to us. For example, information from multiple protein databases (e.g., Swiss-Prot and PDB) might need to be composed to answer queries posed by end-users. Problems of heterogeneity in hardware, operating systems, interfaces and data structures have been widely addressed, but issues of diverse semantics have been handled mainly in an ad-hoc fashion. This paper highlights the ONION (ONtology compositION) system that enables semantic interoperation among various information sources by articulating the ontologies associated with them. An articulation focuses on the semantically relevant intersection of information resources. Although the generation of articulations (semantic correspondences between the ontologies) cannot be fully automated, we take a semi-automatic approach. ONION uses heuristic algorithms for the automatic generation of suggested articulations. This paper outlines an algebra for ontology composition based on their articulations. We show the properties of the algebraic operators and how they depend upon the articulation functions that generate the articulations. Query optimization is enabled based on the properties of the algebraic operators.
A Scalable Framework for the Interoperation of Information Sources.
.  Resolving heterogeneity among information systems is a crucial problem if we  wish to gain value from the many distributed resources available to us. Problems of  heterogeneity in hardware, operating systems, and data structures have been widely  addressed, but issues of diverse semantics have been handled mainly in an ad-hoc  fashion. In this paper, we present ONION, a system based a scalable approach to  interoperation of information systems by articulating their associated ontologies. An  articulation focuses on the semantically relevant intersection of information resources  with respect to a type of application. However, ontologies obtained from diverse sources  are represented using different conceptual models. We have designed a simple intermediate  conceptual model - the ONION conceptual model - that we use to transform  ontologies into before we generate semantic correspondences or articulations between  them.  In ONION, application-dependent articulation rules that capture the correspondence  between concepts in different ontologies are established between source ontologies  semi-automatically. Finally we present an ontology algebra, based on the  articulation rules, for the composition of ontologies.  1 
An Information Food Chain for Advanced Applications on the WWW.
The Internet and especially the World Wide Web are growing at a tremendous rate. More and more information is becoming directly available for human consumption. But humans have a limited information processing capacity and are often not able to find and process the relevant information. Automation, in the form of processing agents that provide a powerful extension to human capabilities, is required. However, with the current technology it is difficult and expensive to build such automated agents and support human user with their information processing power, since agents are not able to understand the meaning of the natural language terms found on todays&#039; webpages. The remedy this situation we look at different existing technologies and put them together to a new information food chain [Etzioni 1997] for agents, that enables advanced applications on the WWW.
A Scalable Framework for the Interoperation of Information Sources.
.  Resolving heterogeneity among information systems is a crucial problem if we  wish to gain value from the many distributed resources available to us. Problems of  heterogeneity in hardware, operating systems, and data structures have been widely  addressed, but issues of diverse semantics have been handled mainly in an ad-hoc  fashion. In this paper, we present ONION, a system based a scalable approach to  interoperation of information systems by articulating their associated ontologies. An  articulation focuses on the semantically relevant intersection of information resources  with respect to a type of application. However, ontologies obtained from diverse sources  are represented using different conceptual models. We have designed a simple intermediate  conceptual model - the ONION conceptual model - that we use to transform  ontologies into before we generate semantic correspondences or articulations between  them.  In ONION, application-dependent articulation rules that capture the correspondence  between concepts in different ontologies are established between source ontologies  semi-automatically. Finally we present an ontology algebra, based on the  articulation rules, for the composition of ontologies.  1 
An Information Food Chain for Advanced Applications on the WWW.
The Internet and especially the World Wide Web are growing at a tremendous rate. More and more information is becoming directly available for human consumption. But humans have a limited information processing capacity and are often not able to find and process the relevant information. Automation, in the form of processing agents that provide a powerful extension to human capabilities, is required. However, with the current technology it is difficult and expensive to build such automated agents and support human user with their information processing power, since agents are not able to understand the meaning of the natural language terms found on todays&#039; webpages. The remedy this situation we look at different existing technologies and put them together to a new information food chain [Etzioni 1997] for agents, that enables advanced applications on the WWW.
Framework for the Semantic Web An RDF Tutorial.

A Graph%2DOriented Model for Articulation of Ontology Interdependencies.
Ontologies explicate the contents, essential properties, and relationships between terms in a knowledge base. Many sources are now accessible with associated ontologies. Most prior work on the use of ontologies relies on the construction of a single global ontology covering all sources. Such an approach is not scalable and maintainable especially when the sources change frequently. We propose a scalable and easily maintainable approach based on the interoperation of ontologies. To handle user queries crossing the boundaries of the underlying information systems, the interoperation between the ontologies should be precisely defined. Our approach is to use rules that cross the semantic gap by creating an articulation or linkage between the systems. The rules are generated using a semi-automatic articulation tool with the help of a domain expert. To make the ontologies amenable for automatic composition, based on the accumulated knowledge rules, we represent them using a gr...
Framework for the Semantic Web An RDF Tutorial.

Multiobjective Search in VLSI Design.

